719. 找出第 k 小的距离对

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

示例 1:

输入：
nums = [1,3,1]
k = 1

输出：0 

解释：
所有数对如下：
(1,3) -> 2

(1,1) -> 0

(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。

提示:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance

思路及算法

• 确定距离差的范围

最小的肯定是0，最大的差则是最大值-最小值.

# 对原数组进行升序排序
nums = sorted(nums)
# 确定距离差的范围
min_distance, max_distance = 0, nums[-1] - nums[0]

• 计算满足当前距离差需要多少对数

从距离差的范围内取出一个距离差值，然后计算这个距离差值前面还有多少对数

# target 距离差值
def count_mid_distance(nums, target):
    """
    :params nums 排序后的数组
    :params target 距离差值
    """
    # 定义left指针，后续
    left, right = 0, 1
    count = 0
    while right < len(nums):
        
        # 差值越大，说明left越小，也就是需要缩小差值，则需要让left向右移动
        # 所以计算出差值大于target的对数
        while nums[right] - nums[left] > target:
            left += 1
        count += right - left
        
        # 进行下一个数字的组合
        right += 1
    return count

• 使用二分查找，找到合适的距离差

找到一个距离差之后，代入计算当前距离差的count函数，然后比较 count 与 k的大小关系，再进一步的去筛选符合要求的距离差，最终会得到一个唯一的距离差

def smallestDistancePair(self, nums: list, k: int) -> int:
    # 对原数组进行升序排序
    nums.sort()
    # 确定距离差的范围
    min_distance, max_distance = 0, nums[-1] - nums[0]
    low, high = min_distance, max_distance
    while low < high:
        mid_distance = (low + high) >> 1
        count = count_mid_distance(nums, mid_distance)
        if count < k:
            low = mid_distance + 1
        elif count >= k:
            high = mid_distance
    return low

代码

class Solution:
    def smallestDistancePair(self, nums: list, k: int) -> int:
        nums.sort()
        min_distance, max_distance = 0, nums[-1] - nums[0]
        low, high = min_distance, max_distance
        while low < high:
            mid_distance = (low + high) >> 1
            # 淘汰策略
            # 对于mid而言
            # 若小于mid的距离差总数 >= k，则距离差应落在 [low, mid] 之间
            # 若大于mid的距离差总数 < k，则距离差应落在 [mid+1, high] 之间
            count = self.count_mid_distance(nums, mid_distance)
            if count >= k:
                high = mid_distance
            else:
                low = mid_distance + 1
        return low

    def count_mid_distance(self, nums: list, target: int) -> int:
        """
        求出满足target距离差的数对个数
        :params nums 排序后的数组
        :params target 距离差值
        """
        size = len(nums)
        count = 0
        left, right = 0, 1
        while right < size:
            # 我们需要知道的是 差值 <= target的数量
            # 注意注意： left的越小，才会导致差值越大
            # 所以left需要不断向右移动，以满足差值 <= target
            while nums[right] - nums[left] > target:
                left += 1
            count += right - left
            right += 1
        return count